import java.util.ArrayList;
import java.util.Random;
import java.util.zip.CheckedOutputStream;


/**
 * @author minasora
 * @date 2019/10/7 16:16
 * @description 提供了crossover，mutation，selection等遗传算法使用的函数
 */
public class GA_Strategy {
    public static double p_rate = 0.1;
    public static int pop_number = 100;// 种群的数量

    /**
     * 初始化种群
     *
     * @return 返回初始种群
     */
    static Chromosome[] initialize() {
        Chromosome[] chromosomes = new Chromosome[pop_number];
        for (int i = 0; i < pop_number; i++) {
            chromosomes[i] = new Chromosome();
            chromosomes[i].setFitness();
        }
        return chromosomes;
    }


    /**
     * 交叉算子
     * OX交叉方式，返回一个新的Chromosome，交换亲代即可获得两个子代
     *
     * @param p_one 父代一
     * @param p_two 父代二
     * @return 交叉得到的子代
     */
    static Chromosome crossover(Chromosome p_one, Chromosome p_two) {

        // 1.准备工作
        Chromosome children = new Chromosome();
        children.cur_list.clear();
        children.cur_list.add(0); // 从仓库出发

        // 2.得到交叉点的位置，获得 0<= i<= j <= n的随机数
        Random r = new Random();
        int i = r.nextInt(Conf.N) + 1;
        int j = r.nextInt(Conf.N) + 1;
        if (j < i) {
            int mid = i;
            i = j;
            j = mid;
        }

        // 3.执行OX交叉操作
        //  3.1 把i-j中的点先转移到children中
        for (int tmp = i; tmp <= j; tmp++)
            children.cur_list.add(p_one.cur_list.get(tmp));
        //  3.2 parent存储p_two中其他位置的染色体
        ArrayList<Integer> parent = new ArrayList<>();
        for (int tmp = j; tmp <= Conf.N; tmp++)
            parent.add(p_two.cur_list.get(tmp));
        for (int tmp = 1; tmp <= j; tmp++)
            parent.add(p_two.cur_list.get(tmp));
        //  3.3 将parent中的染色体按照规则插入到children中
        int tmp = j; // 在子代基因位的索引
        Boolean if_fir = false;//标记是否到了子代基因位的末尾
        for (int t : parent) {
            if (tmp == Conf.N)//假如到了末尾
            {
                tmp = 1;//从头开始
                if_fir = true;
            }
            if (if_fir) {
                if (!children.cur_list.contains(t)) {
                    children.cur_list.add(1, t);
                    tmp++;
                }
            } else {
                if (!children.cur_list.contains(t))//不包含的话就加入
                {
                    children.cur_list.add(t);
                    tmp++;
                }
            }
        }
        // 4.设置适应度
        children.setFitness();
        return children;
    }

    /**
     * 突变算子
     * 直到突变出比原来个体适应度更好的个体后，才可以停止突变
     *
     * @param chromosome
     * @return
     */
    static Chromosome mutation(Chromosome chromosome) {
        Chromosome new_chromosome = chromosome.copy();
        int iteratiion = 1;
        while (iteratiion < 10000) {
            if (chromosome.fitness > neighborhood_move(new_chromosome).fitness) {
                return new_chromosome;
            } else
                new_chromosome = chromosome.copy();
        }
        return new_chromosome;
    }

    /**
     * 对解（染色体）进行邻域搜索
     * 随机交换染色体中两个基因位的位置
     *
     * @param chromosome 原染色体
     * @return
     */
    static Chromosome neighborhood_move(Chromosome chromosome) {
        Random r = new Random();
        int i = r.nextInt(Conf.N) + 1;
        int j = r.nextInt(Conf.N) + 1;
        int mid = chromosome.cur_list.get(i);
        chromosome.cur_list.set(i, chromosome.cur_list.get(j));
        chromosome.cur_list.set(j, mid);
        chromosome.setFitness();
        return chromosome;
    }

    /**
     * 选择算子，保留优秀个体，二进制锦标赛选择
     * 这个是直接生成子代
     *
     * @param chromosomes
     * @return
     */
    static Chromosome[] selection(Chromosome[] chromosomes) {
        Chromosome[] childrens = new Chromosome[pop_number];
        for (int t = 0; t < pop_number; t++) {
            Random r = new Random();
            int i = r.nextInt(pop_number);
            int j = r.nextInt(pop_number);
            if (chromosomes[i].fitness < chromosomes[j].fitness)
                childrens[t] = chromosomes[i];
            else
                childrens[t] = chromosomes[j];
        }
        return childrens;
    }

    /**
     * 获取种群中的最优个体
     *
     * @param chromosomes
     * @return
     */
    static Chromosome getbest(Chromosome[] chromosomes) {
        Chromosome chromosome = null;
        double min = 99999;
        for (int i = 0; i < pop_number; i++) {
            if (min > chromosomes[i].fitness) {
                min = chromosomes[i].fitness;
                chromosome = chromosomes[i];
            }
        }
        return chromosome;
    }

    static double get_mean(Chromosome[] chromosomes) {
        double ans = 0;
        for (Chromosome chromosome : chromosomes) {
            ans += chromosome.fitness;
        }
        return ans / pop_number;
    }


    /**
     * 遗传算法主流程
     *
     * @return 返回种群中的最佳染色体
     */
    static Chromosome genetic_algoritm() {
        Chromosome best = new Chromosome();
        double min = 999999;

        // 1.初始化种群（每个种群个体又可以初始化自己的染色体基因序列，即每个个体做出一个初始解）
        Chromosome[] parents = GA_Strategy.initialize();

        // 2.进行遗传算法操作（迭代1000次）
        for (int i = 1; i <= 1000; i++) {
            Chromosome[] childrens = new Chromosome[pop_number];//子代数组

            // 2.1 选择算子，选择出来的是一个数量为N的种群
            Chromosome[] mid = GA_Strategy.selection(parents);
            // 2.2 交叉算子
            for (int j = 0; j < pop_number; j++) {
                Random r = new Random();
                int fir = r.nextInt(pop_number);
                int sec = r.nextInt(pop_number);
                childrens[j] = crossover(mid[fir], mid[sec]);
            }
            // 2.3 变异算子
            for (int p = 0; p < pop_number; p++) {
                childrens[p] = mutation(childrens[p]);
            }
            // 2.4 用新的种群替代原来的种群
            for (int q = 0; q < pop_number; q++) {
                parents[q] = childrens[q];
            }
            // 2.5 记录当前种群中的最优个体
            if (min > GA_Strategy.getbest(parents).fitness) {
                best = GA_Strategy.getbest(parents);
                min = best.fitness;
            }
        }
        return best;
    }
}